USACO2014Jan-Moolympics区间记录优化算法

 1 #include 
 2 #include 
 3 using namespace std;
 4 
 5 const int N = 155;
 6 struct Interval { int l, r; } intervals[N];
 7 
 8 bool compare(Interval x, Interval y) { return x.r  9 
10 int main() {
11     int n;
12     scanf("%d", &n);
13     for (int i = 0; i 14         scanf("%d %d", &intervals[i].l, &intervals[i].r);
15         if (intervals[i].l > intervals[i].r) swap(intervals[i].l, intervals[i].r);
16     }
17     sort(intervals, intervals + n, compare);
18     int count = 0, end1 = 0, end2 = 0;
19     for (int i = 0; i 20         if (end1 <= intervals[i].l) {
21             ++count;
22             end1 = intervals[i].r;
23         } else if (end2 <= intervals[i].l) {
24             ++count;
25             end2 = intervals[i].r;
26         }
27         if (end1 > end2) swap(end1, end2);
28     }
29     printf("%d
", count);
30     return 0;
31 }